package sword.T7;

import util.TreeNode;

/**
 * @File Info: leetcode -- <Solution>
 * @Author: 18362
 * @Create: 2022-03-23 1:39:55 星期三
 */

class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return build(preorder, inorder, 0, preorder.length-1, 0, inorder.length-1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int pl, int pr, int il, int ir) {
        if (pl > pr)
            return null;
        TreeNode root = new TreeNode(preorder[pl]);
        int k = 0;
        for (int i=il; i<=ir; ++i) {
            if (inorder[i] == preorder[pl]) {
                k = i;
                break;
            }
        }
        root.left = build(preorder, inorder, pl+1, k-il+pl, il, k-1);
        root.right = build(preorder, inorder, k-il+pl+1, pr, k+1, ir);
        return root;
    }
}